//给定一个二维矩阵 matrix，以下类型的多个请求：
//
//
// 计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。
//
//
// 实现 NumMatrix 类：
//
//
// NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
// int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角
// (row2, col2) 的子矩阵的元素总和。
//
//
//
//
// 示例 1：
//
//
//
//
//输入:
//["NumMatrix","sumRegion","sumRegion","sumRegion"]
//[[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,
//1,2,2],[1,2,2,4]]
//输出:
//[null, 8, 11, 12]
//
//解释:
//NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,
//0,1,7],[1,0,3,0,5]]]);
//numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
//numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
//numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)
//
//
//
//
// 提示：
//
//
// m == matrix.length
// n == matrix[i].length
// 1 <= m, n <= 200
//
// -10⁵ <= matrix[i][j] <= 10⁵
// 0 <= row1 <= row2 < m
// 0 <= col1 <= col2 < n
//
// 最多调用 10⁴ 次 sumRegion 方法
//
//
//
//
//
// 注意：本题与主站 304 题相同： https://leetcode-cn.com/problems/range-sum-query-2d-
//immutable/
//
// Related Topics 设计 数组 矩阵 前缀和 👍 84 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
//? 暴力
class NumMatrix {
    arr : number[][]
    count : number
    constructor(matrix: number[][]) {
        this.arr = matrix
        this.count = 0
    }

    sumRegion(row1: number, col1: number, row2: number, col2: number): number {
        this.count = 0
        for (let i = row1; i <= row2; i ++) {
            for (let j = col1; j <= col2; j ++) {
                this.count += this.arr[i][j]
            }
        }
        return this.count
    }
}

class NumMatrix2 {
    matrix: number[][];
    pre: number[][];
    constructor(matrix: number[][]) {
        this.matrix = matrix;
        let n = matrix.length;
        let m = matrix[0].length;
        this.pre = new Array(n).fill(0).map((val) => new Array(m).fill(0));
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < m; j++) {
                if (j - 1 >= 0){
                    this.pre[i][j] = this.pre[i][j - 1] + matrix[i][j];
                }
                else this.pre[i][j] = matrix[i][j];
            }
        }
    }

    sumRegion(row1: number, col1: number, row2: number, col2: number): number {
        let sum = 0;
        for (let i = row1; i <= row2; i++) {
            //? 因为pre是累加的矩阵 所以减掉 拿到一行的总和
            if (col1 - 1 >= 0) sum += this.pre[i][col2] - this.pre[i][col1 - 1];
            else sum += this.pre[i][col2];
        }
        return sum;
    }
}
